/********************************************************************************
TITLE:                      	Formatted Output
FILENAME:                   	T_List.cpp
PREPARED FOR:               	CS215 Section CS13-02
PROGRAMMER(S):              	Eric (Fox) Crowell, (Timothy Drye)
DEVELOPMENT DATE:           	< 12/15/13 >
COMPILER USED:      			Microsoft Visual Studio Professional 2013
- Version 12.0.21005.1 REL
TARGET PLATFORM:         	    Windows 8 x64
================================================================================
REVISION HISTORY

DATE         PROGRAMMER          DESCRIPTION OF CHANGES MADE
------------------------------------------------------------------------------
<12/15/13       Tim                 CPP File created.                        >
<12/16/13       Fox                 Inserted scope resolution operators for
                                    most functions.                          >
<12/16/13       Fox                 Removed un-used includes.                >
<12/16/13       Fox                 Fixed code to match task directions.     >
*******************************************************************************/

// Doubles the memory allocation of pList and Capacity value.
#include "T_List.h"

// Default constructor [Fox]
template<typename T>
T_List<T>::T_List() {
	// "Capacity" defautls to 5. [Fox]
	Capacity = 5;
	// "Occupancy" starts at 0 (No items). [Fox]
	Occupancy = 0;
	// Initalized the "pList" data mamber as an array with the default size of "Capacity" [Fox]
	pList = new T[Capacity];
	assert(0 != pList); // Ensure data was allocated. [Fox]
}

// Overloaded constructor. [Fox]
template<typename T>
T_List<T>::T_List(int initSize) {
	// "Capacity" starts a "initSize" (always greater than 0). [Fox]
	Capacity = initSize > 0 ? initSize : 1;
	// "Occupancy" starts at 0 (No items). [Fox]
	Occupancy = 0;
	// Initalized the "pList" data mamber as an array of "initSize" length [Fox]
	pList = new T[Capacity];
}

// Inserts in a new item [Fox]
template<typename T>
void T_List<T>::Insert(const T & item) {
	// if the Occupancy is equal to, and hopefully never greater than, Capacity
	//      call the expand memeber function to make room for more. [Fox]
	if (Occupancy >= Capacity) {
		Expand();
	}

	pList[Occupancy] = item; // Put the item in the list [Fox]
	Occupancy++; // Increment Occupancy by one. [Fox]
}

// Searches the list for an object identical to the template type passed as a parameter
//      to this function and then, if found, remove it and adjust the list to fill in
//      the empty hole. [Fox]
template<typename T>
bool T_List<T>::Remove(const T & item) {
	// First, search for the item. [Fox]
	for (int i = 0; i < Occupancy; i++){
		// If the address of pList[i] is the same as the address of item, remove it,
		//     fill in the gap, and exit out of this function. [Fox]
		if (pList[i] == item){
			// Filling in the gap at this index will remove it.
			for (int j = i; j < (Occupancy - 1); j++){
				pList[j] = pList[j + 1];
			}
			// Data still exists in the last index of pList, however, it's not necessary
			//     to actually delete it. We just need to set the Occupancy back one. [Fox]
			// Further insertions will eventually overwrite it or Shrink()s will delete it. [Fox]
			Occupancy--;
			// Check if the Occupany is half the Capacity (Remainder dropped)
			if (Capacity > 1 && Occupancy <= static_cast<int>(Capacity / 2)) {
				Shrink();
			}
			// Exit out of the function. We're done here. [Fox]
			// Since we found the item, return true. [Fox]
			return(true);
		}
	}
	// The loop completed. This means the item was not found in the list. [Fox]
	// Return false. [Fox]
	return(false);
}

// Returns the number of items occupying this list. [Fox]
template<typename T>
int T_List<T>::NumInList(const T & item) const {
	return(Occupancy);
}

// Returns TRUE if this T_List contains no items... Otherwise, returns FALSE [Tim, Fox]
template<typename T>
bool T_List<T>::IsEmpty() const {
	return(Occupancy == 0);
}

// Displays all items in this T_List. [Fox]
template<typename T>
void T_List<T>::Display() const {
	cout << "T_List contents\n";
	cout << "----------------------------------------\n";
	// If the T_List is empty, output a message stating so. [Tim, Fox]
	if (IsEmpty()) {
		cout << "[No items to display]\n";
	// Otherwise, start a loop to print out the rest T_List data. [Fox]
	} else {
		for (int i = 0; i < Occupancy; i++){
			cout << "[" << (i+1) << "]\t" << pList[i] << "\n";
		}
	}
	cout << "----------------------------------------\n";
}

// Expands the list. [Fox]
template<typename T>
void T_List<T>::Expand() {
	T * pTemp; // Create a temporary pointer pointing to the extended array. [Fox]
	pTemp = new T[Capacity * 2]; // Extension is current Capacity * 2; [Fox]
	assert(0 != pTemp); // Ensure the new data was allocated. [Fox]

	// Copy over the data in pList to the temporary, larger, pointer array.
	for (int i = 0; i < Capacity; i++) {
		pTemp[i] = pList[i];
	}

	// Delete the pList data. [Fox]
	delete[] pList;
	// Double to Capacity data member. [Fox]
	Capacity = Capacity * 2;
	pList = pTemp;

	cout << "Expanded to " << Capacity << "\n";
}

// Shrinks the list. [Fox]
template<typename T>
void T_List<T>::Shrink() {
	T * pTemp; // Create a temporary pointer pointing to the extended array. [Fox]
	pTemp = new T[static_cast<int>(Capacity / 2)]; // Shrink is current this->Capacity / 2 (Remainder dropped). [Fox]
	assert(0 != pTemp); // Ensure the new data was allocated. [Fox]

	// Copy over the data in pList to the temporary, larger, pointer array. [Fox]
	for (int i = 0; i < Occupancy; i++) {
		pTemp[i] = pList[i];
	}

	// Delete the pList data. [Fox]
	delete[] pList;
	// Half to Capacity data member. [Fox]
	Capacity = static_cast<int>(Capacity / 2);
	pList = pTemp;

	cout << "Shrunk to " << Capacity << "\n";
}